/*
力扣(210.课程表2)题目链接:https://leetcode.cn/problems/course-schedule-ii/description/
*/
class Solution {
public:
	vector<vector<int>> g;
	vector<int> ind,sorted; //每个节点的入度和已经拓扑排序好的数组
	int n,m;
	void init(int n, vector<vector<int>>& gg){ //初始化每个节点的入度
		this->n=n,m=gg.size(),ind.resize(n),g.resize(n),sorted.reserve(n);
		for(int i=0;i<m;i++){
			int u=gg[i][0],v=gg[i][1];
			g[v].push_back(u); //v需要排在u之前
			ind[u]++; //u的入度加1
		}
	}
	void cl(){ //kathy算法核心
		deque<int> q;
		for(int i=0;i<n;i++){ //先将每个入度为0的节点压入队列
			if(!ind[i]){
				q.push_back(i);
			}
		}
		while(!q.empty()){
			int u=q.front(); 
			q.pop_front();
			if(!ind[u]){ //若当前节点入度已经为0则添加到已添加序列中
				sorted.push_back(u);
			}
			for(int i=0;i<g[u].size();i++){ //遍历当前节点的所指向的节点
				int v=g[u][i];
				ind[v]--; //将当前节点对所指向的节点影响去除 将其入度减1
				if(!ind[v]){ //若该被指向节点入度为0添加到队列中
					q.push_back(v);
				}
			}
		}
	}
    vector<int> findOrder(int n, vector<vector<int>>& gg) { //gg为依赖关系 n为课程总数
		init(n,gg);
		cl();
		if(sorted.size()<n){ //若已被排序序列中元素数小于总的节点数 则说明依赖关系存在环 不成立
			return vector<int>(0);
		}else{
			return sorted;
		}
    }
};
